package class02;

import java.util.Random;

/**
 * @description: 前缀和数组
 * @time: 2021/7/5 20:59
 * @author: lhy
 */
public class PrefixSum {

    static class RangeSum1{
        private final int[] array;

        public RangeSum1(int[] array) {
            this.array = array;
        }
        public int rangeSum(int left, int right){
            int sum = 0;
            for (int i = left; i <= right ; i++) {
                sum += array[i];
            }
            return sum;
        }

    }

    static class RangeSum2{
        private final int[] prefixSum;
        public RangeSum2(int[] array){
            int len = array.length;
            prefixSum = new int[len];
            prefixSum[0] = array[0];
            for (int i = 1; i < len; i++) {
                prefixSum[i] = prefixSum[i-1] + array[i];
            }
        }

        public int rangeSum(int left, int right){
            return left == 0 ? prefixSum[right] : prefixSum[right] - prefixSum[left-1];
        }
    }

    static class RangeSum3{
        final int[][] tableSumArray;
        public RangeSum3(int[] array, int[][] tableSumArray) {
            this.tableSumArray = tableSumArray;
            int len = array.length;
            for (int i = 0; i < len; i++) {
                this.tableSumArray[i][i] = array[i];
                for (int j = i+1; j < len; j++) {
                    this.tableSumArray[i][j] = this.tableSumArray[i][j-1] + array[j];
                }
            }
        }
        public int rangeSum(int[][] tableSumArray,int left, int right){
            return tableSumArray[left][right];
        }
        public void printArray2(int[][] tableSumArray,int len){
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    System.out.print(tableSumArray[i][j] + " ");
                }
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[10000];
        int len = arr.length;
        int randomLen = len / 2;
        for (int i = 0; i < len; i++) {
            arr[i] = i+1;
        }
        int l,r;
        int testTimes = 999999999;
        int ans = 0;
        Random random = new Random();
        l = random.nextInt(randomLen);
        r = random.nextInt(randomLen) + l;
        // test RangSum1
        RangeSum1 rangeSum1 = new RangeSum1(arr);
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < testTimes; i++) {
            ans = rangeSum1.rangeSum(l,r);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("rangeSum1 time:" + (endTime - startTime));

        // test RangSum2
        RangeSum2 rangeSum2 = new RangeSum2(arr);
        startTime = System.currentTimeMillis();
        for (int i = 0; i < testTimes; i++) {
            ans = rangeSum2.rangeSum(l,r);
        }
        endTime = System.currentTimeMillis();
        System.out.println("rangeSum2 time:" + (endTime - startTime));

        // test RangSum3
        int[][] tableSumArray = new int[len][len];
        RangeSum3 rangeSum3 = new RangeSum3(arr,tableSumArray);
        startTime = System.currentTimeMillis();
        for (int i = 0; i < testTimes; i++) {
            ans = rangeSum3.rangeSum(tableSumArray,l,r);
        }
        endTime = System.currentTimeMillis();
        System.out.println("rangeSum3 time:" + (endTime - startTime));

    }
}
